#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
    int data;
    struct Node *next;
    struct Node *prev;
} Node_t, *Node_p;

Node_p newNode(int data)
{
    Node_p node = (Node_p)malloc(sizeof(Node_t));
    node->data = data;
    node->next = NULL;
    node->prev = NULL;
    return node;
}

void teaverse(Node_p head)
{
    Node_p p = head->next;
    while (p != head)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

void reversedTeaverse(Node_p head)
{
    Node_p p = head->prev;
    while (p != head)
    {
        printf("%d ", p->data);
        p = p->prev;
    }
    printf("\n");
}

void insertTail(Node_p head, int data)
{
    Node_p node = newNode(data);
    Node_p p = head->prev;
    p->next = node;
    node->prev = p;
    node->next = head;
    head->prev = node;
}

void insertHead(Node_p head, int data)
{
    Node_p node = newNode(data);
    Node_p p = head->next;
    node->next = head->next;
    head->next->prev = node;
    node->prev = head;
    head->next = node;
}

void traverseCount(Node_p head, int n)
{
    Node_p p = head->next;
    while (n--)
    {

        if (p == head)
        {
            printf("%d ", p->next->data);
            p = p->next->next;
        }
        else
        {
            printf("%d ", p->data);
            p = p->next;
        }
    }
    printf("\n");
}

void destory(Node_p *head)
{
    Node_p p = (*head)->next;
    while (p != *head)
    {
        Node_p q = p;
        p = p->next;
        free(q);
    }
    free(*head);
    *head = NULL;
}

int main()
{
    printf("%d\n", sizeof(Node_t));

    Node_p head = newNode(0);
    head->next = head;
    head->prev = head;

    Node_p node1 = newNode(22);
    Node_p node2 = newNode(33);
    Node_p node3 = newNode(44);

    head->next = node1;
    node1->next = node2;
    node2->next = node3;
    node3->next = head;

    node3->prev = node2;
    node2->prev = node1;
    node1->prev = head;
    head->prev = node3;

    insertHead(head, 11);
    insertTail(head, 55);

    // teaverse(head);
    // reversedTeaverse(head);
    traverseCount(head, 21);

    destory(&head);

    printf("%p\n", head);

    return 0;
}